#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<map>
using namespace std;




//dfs解法（逻辑正确，但是解法超时，最短问题不适合用dfs）
// class Solution1 {
//     bool check[101][101]={};
//     vector<vector<int>> memo[101][101];
//     int ret=INT_MAX;
//     int path=0;
//     int m;int n;
//     int dx[4]={0,0,-1,1};
//     int dy[4]={-1,1,0,0};
//     int initx;int inity;
// public:
//     int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) 
//     {
//         m=maze.size();
//         n=maze[0].size();
//         initx=entrance[0];
//         inity=entrance[1];
//         dfs(maze,entrance[0],entrance[1]);
//         if(ret==INT_MAX)    return -1;
//         else return ret;
//     }
//     void dfs(vector<vector<char>>& maze,int i,int j)
//     {
//         if((i==0||j==0||i==m-1||j==n-1)&&(i!=initx||j!=inity))
//         {
//             //cout<<i<<" "<<j<<" "<<initx<<" "<<inity<<" ";
//             ret=ret<path?ret:path;
//             return;
//         }
//         for(int k=0;k<4;k++)
//         {
//             int x=i+dx[k];int y=j+dy[k];
//             if(x>=0&&x<m&&y>=0&&y<n&&maze[x][y]=='.'&&check[x][y]==false)
//             {
//                 path++;
//                 check[x][y]=true;
//                 dfs(maze,x,y);
//                 path--;
//                 check[x][y]=false;
//             }
//         }
//     }
// };


//BFS解决最短路问题01：迷宫中离入口最近的出口
class Solution1 {
    bool check[101][101]={};
    int dx[4]={0,0,-1,1};
    int dy[4]={-1,1,0,0};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) 
    {
        int m=maze.size();int n=maze[0].size();
        int ret=0;
        queue<pair<int,int>>  q;
        q.push(pair<int,int>{entrance[0],entrance[1]});
        check[entrance[0]][entrance[1]]=true;
        while(!q.empty())
        {
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                auto [a,b]=q.front(); //c+17语法支持，结构化绑定
                //int a=q.front().first;
                //int b=q.front().second;
                if((a!=entrance[0]||b!=entrance[1])&&(a==0||b==0||a==m-1||b==n-1))    return ret;
                q.pop();
                for(int j=0;j<4;j++)
                {
                    int x=a+dx[j];
                    int y=b+dy[j];
                    if(x>=0&&y>=0&&x<m&&y<n&&maze[x][y]=='.'&&check[x][y]==false)
                    {
                        q.push({x,y});
                        check[x][y]=true;
                    }
                }
            }
            ret++;
        }
        return -1;
    }
};


//BFS解决最短路问题02：最小基因变化
class Solution2 {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) 
    {
        int ret=0;
        int n=startGene.size();
        string gene{"ACGT"};
        queue<string> q({startGene});
        unordered_map<string,int> hash;
        for(auto& it:bank)
        {
            hash[it]++;
        }
        unordered_map<string,int> vis;
        while(!q.empty())
        {
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                if(q.front()==endGene)
                    return ret;
                for(int j=0;j<n;j++)
                {
                    string tmp=q.front();
                    for(auto& it:gene)
                    {
                        tmp[j]=it;
                        if(hash.count(tmp)&&!vis.count(tmp))
                        {
                            vis[tmp]++;
                            q.push(tmp);
                        }
                    }
                }
                q.pop();
            }
            ret++;
        }
        return -1;    
    }
};

//BFS解决最短路问题03：单词接龙（双向BFS算法）
class Solution3 {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        int ret=1;
        // int n=0;
        // for(auto& it:wordList)
        // {
        //     if(it==endWord)n++;
        // }
        // if(n==0)    return n;
        // int ret=1;
        // unordered_map<string,vector<string>> dic;
        // for(int i=0;i<wordList.size();i++)
        // {
        //     for(int j=0;j<wordList[0].size();j++)
        //     {
        //         auto tmp=wordList[i];
        //         tmp[j]='*';
        //         dic[tmp].push_back(wordList[i]);
        //     }
        // }
        unordered_set<string> dic(wordList.begin(),wordList.end());
        if(!dic.count(endWord)) return 0;
        unordered_set<string> check;
        //queue<string> q({beginWord});
        unordered_set<string> star({beginWord});
        unordered_set<string> end({endWord});
        while(!star.empty()&&!end.empty())
        {
            if(star.size()>end.size()) swap(star,end);
            //int size=star.size();
            unordered_set<string>   next;
            for(auto top:star)
            {
                //auto top=star[i];
                for(int j=0;j<top.size();j++)
                {
                    auto tmp=top;
                    for(char c='a';c<='z';c++)
                    {
                        tmp[j]=c;
                        if(end.count(tmp))   return ret+1;
                        if(dic.count(tmp)&&!check.count(tmp))
                        {
                            if(!check.count(tmp))
                            {
                                next.insert(tmp);
                                check.insert(tmp);
                            }
                        }
                    }

                }
            }
            star=next;
            ret++;
        }
        return 0;
    }
};

class Solution4 {
    int dx[4]={0,0,-1,1};
    int dy[4]={-1,1,0,0};
public:
    int cutOffTree(vector<vector<int>>& forest) 
    {
        if(forest[0][0]==0) return -1;
        if(forest.empty())  return 0;
        int m=forest.size();int n=forest[0].size();
        int ret=0;
        queue<pair<pair<int,int>,int>> q;//存坐标和对应位置的数字。
        q.push({{0,0},forest[0][0]});
        vector<vector<int>> trees;
        //unordered_map<int,pair<int,int>> trees;
        for(int i=0;i<forest.size();i++)
        {
            for(int j=0;j<forest[0].size();j++)
            {
                if(forest[i][j]>=2)
                {
                    trees.push_back({forest[i][j],i,j});
                    //trees[forest[i][j]]={i,j};
                }
            }
        }
        sort(trees.begin(),trees.end());
        //int n=0;
        int i=0;
        for(i;i<trees.size();i++)
        {
            //int target=trees[i];
            bool check[51][51]={};
            int path=0;
            while(!q.empty())
            {
                int size=q.size();
                for(int j=0;j<size;j++)
                {
                    if(q.front().first.first==0&&q.front().first.second==2)
                        int f=4;
                    auto top=q.front();//top是一个pair<pair<int,int>，int>;
                    if(top.first.first==trees[i][1]&&top.first.second==trees[i][2])
                    {
                        ret+=path;
                        forest[trees[i][1]][trees[i][2]]=1;
                        goto outer;
                    } 
                    check[top.first.first][top.first.second]=true;
                    q.pop();
                    for(int k=0;k<4;k++)
                    {
                        int x=dx[k]+top.first.first;
                        int y=dy[k]+top.first.second;
                        if(x>=0&&y>=0&&x<m&&y<n&&(forest[x][y]!=0)&&check[x][y]==false)
                        {
                            check[x][y]=true;
                            //count++;
                            q.push({{x,y},forest[x][y]});
                        }
                    }
                    // if(count==0)
                    // {
                    //     cout<<1<<":"<<ret;
                    //     return -1;
                    // }    
                }
                //cout<<"2"<<":"<<path;
                path++;
            }
            
            if(q.empty())   return -1;
            outer:
            //cout<<"1"<<":"<<path;
        }
        //if(i!=trees.size()) return -1;
        //else
        return ret;
    }
};


void test3()
{
    vector<vector<int>> forest = {
    {54581641, 64080174, 24346381, 69107959},
    {86374198, 61363882, 68783324, 79706116},
    {668150, 92178815, 89819108, 94701471},
    {83920491, 22724204, 46281641, 47531096},
    {89078499, 18904913, 25462145, 60813308}
};
    Solution4 SL;
    SL.cutOffTree(forest);
    cout<<"succ"<<endl;
}


void test1()
{
    Solution2 SL;
    string starGene="AACCGGTT";
    string endGene="AACCGGTA";
    vector<string> bank={"AACCGGTA"};
    cout<<SL.minMutation(starGene,endGene,bank)<<endl;
}

void test2()
{
    string begin="hit";
    string end="cog";
    vector<string>  list={"hot","dot","dog","lot","log","cog"};
    Solution3 SL;
    SL.ladderLength(begin,end,list);
    cout<<"success"<<endl;
}



int main()
{

    test3();
    return 0;
}